#include <iostream>
#include <vector>

// 数组划分和数组分块最核心的解法就是双指针法
// 力扣283移动零

// 通过两个指针，一个指针找到零后停下，另一个指针找到非零元素后停下，两指针内容交换
// 以此往复
void push_zero_by_zero(std::vector<int> &v)
{
    for (int slow = 0; slow < v.size(); slow++)
    {
        if (v[slow] == 0)
        {
            for (int fast = slow + 1; fast < v.size(); fast++)
            {
                if(v[fast] != 0)
                {
                    std::swap(v[slow], v[fast]);
                    break;
                }
            }
        }
    }
}

/*
void push_zero_by_not_zero(std::vector<int>& v)
{
    //将整个数组分成三部分：slow左面是没有0的，fast右面是未判断的，中间是0
    for(int slow = -1, fast = 0; fast < v.size(); fast++)
    {
        if(v[fast])
        {
            std::swap(v[slow++], v[fast]);
        }
    }
}
*/

void push_zero_by_none_zero(std::vector<int>& v)
{
    //. 非0 ｜ 0 ｜ 未处理的
    for(int des = -1, cur = 0; cur <= v.size(); cur++)
    {
        if(v[cur])
        {
            std::swap(v[cur], v[++des]);
        }
    }
}

int main()
{
    std::vector<int> v = {1, 0, 2, 3, 0, 4, 5, 0};
    push_zero_by_none_zero(v);
    for (auto &e : v)
    {
        std::cout << e << " ";
    }
    return 0;
}

